This invention relates to a multiplier for the multiplication of at least two figures in an original format.
The standard work "Computer Arithmetic" of K. Hwang, J. Wiley & Sons, NY 1979, shows the usual art of applying parallel array multipliers when multiplying digital data. Such array multipliers as shown on page 164 generally have a structure consisting of two main parts. An input part with a 2-dimensional array of n(horizontal) and n(vertical) bitlines corresponding to the two n-bit input operands x and y. At the bitline crossings AND-gates are arranged. For arriving at the multiplied value of the input operands x and y, a processing part applies an array of about n.sup.2 Full-Adders.
This known type of adder array hardware is very inefficient. The multiplication of two n-bit operands requires only one of 2.sup.2n bit patterns being actually processed, whereas the capacity of the array is capable of adding any of the 2.sup.n.n n.times.n bit patterns of n.sup.2 bits.
In order to improve the efficiency of the known multiplier, the known Booth multiplier is applied as shown on page 198 of the above-mentioned citation. In the Booth multiplier, each successive bit-pair of any one operand has a value range {0, 1, 2, 3} wherein 3 is recorded as -1+4. The -1 causes a subtraction of the other operand, while +4, as positive carry into the next bit-pair position, implies an addition, resulting in an effective reduction of the logic depth in the add/subtract array, and a corresponding speed-up at the cost of a more complex recoding of one operand, and extra subtract hardware.